翻訳と辞書
Words near each other
・ Twelve Years a Slave
・ Twelve Years a Slave (disambiguation)
・ Twelve Years Together
・ Twelve Years' Truce
・ Twelve-bar blues
・ Twelve-dish Christmas Eve supper
・ Twelve-Mile Circle
・ Twelve-pound cannon
・ Twelve-spotted skimmer
・ Twelve-step program
・ Twelve-step Suite
・ Twelve-string bass
・ Twelve-string guitar
・ Twelve-tone technique
・ Twelve-wired bird-of-paradise
Twelvefold way
・ Twelvefour
・ Twelveheads
・ Twelveheads Press
・ Twelvemile Corner, Illinois
・ Twelvemile Creek
・ Twelvemile Creek (Mustinka River)
・ Twelvepole Creek
・ Twelver
・ Twelvestep
・ Twelvetrees
・ Twem
・ Twemlow
・ Twemlow (surname)
・ Twemlow Hall


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Twelvefold way : ウィキペディア英語版
Twelvefold way
In combinatorics, the twelvefold way is a name given to a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number. The idea of the classification is credited to Gian-Carlo Rota, and the name was suggested by Joel Spencer.〔Richard P. Stanley (1997). (''Enumerative Combinatorics, Volume I'' ). Cambridge University Press. ISBN 0-521-66351-2. p.41〕
== Overview ==

Let N and X be finite sets. Let n=|N| and x=|X| be the cardinality of the sets. Thus N is an n-set, and X is an x-set.
The general problem we consider is the enumeration of equivalence classes of functions f: N \to X.
The functions are subject to one of the three following restrictions:
# No condition: each a in N may be sent by f to any b in X, and each b may occur multiple times.
# f is injective: each value f(a) for a in N must be distinct from every other, and so each b in X may occur at most once in the image of f.
# f is surjective: for each b in X there must be at least one a in N such that f(a) = b, thus each b will occur at least once in the image of f.
A possible fourth condition of f being bijective is not included, since it doesn't add any new problems (the set of such functions will be empty unless n=x, in which case the condition is both equivalent to f being injective and equivalent to f being surjective).
There are four different equivalence relations which may be defined on the set of functions f from N to X:
# equality;
# equality up to a permutation of N;
# equality up to a permutation of X;
# equality up to permutations of N and X.
Any of these equivalence relations produces a decomposition of the set of functions into equivalence classes.
(An equivalence class is the orbit of a function f under the group action considered: , or , or , or , where is the symmetric group of ''N'', and is the symmetric group of ''X''.)
The three conditions on the functions and the four equivalence relations can be paired in 3 × 4 = 12 ways.
The twelve problems of counting equivalence classes of functions do not involve the same difficulties, and there is not one systematic method for solving them. Two of the problems are trivial (the number of equivalence classes is 0 or 1), five problems have an answer in terms of a multiplicative formula of ''n'' and ''x'', and the remaining five problems have an answer in terms of combinatorial functions (Stirling numbers and the partition function for a given number of parts).
The incorporation of classical enumeration problems into this setting is as follows.
* Counting ''n''-permutations (i.e., partial permutations or sequences without repetition) of ''X'' is equivalent to counting injective functions ''N'' → ''X''.
* Counting ''n''-combinations of ''X'' is equivalent to counting injective functions ''N'' → ''X'' up to permutations of ''N''.
* Counting permutations of the set ''X'' is equivalent to counting injective functions ''N'' → ''X'' when ''n'' = x, and also to counting surjective functions ''N'' → ''X'' when ''n'' = ''x''.
* Counting multisets of size ''n'' (also known as ''n''-combinations with repetitions) of elements in ''X'' is equivalent to counting all functions ''N'' → ''X'' up to permutations of ''N''.
* Counting partitions of the set ''N'' into ''x'' subsets is equivalent to counting all surjective functions ''N'' → ''X'' up to permutations of ''X''.
* Counting compositions of the number ''n'' into ''x'' parts is equivalent to counting all surjective functions ''N'' → ''X'' up to permutations of ''N''.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Twelvefold way」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.